<?php
    class Solution {

        /**
         * 13. 罗马数字转整数
         * @param String $s
         * @return Integer
         */
        function romanToInt13($s) {
            $len = strlen($s);
            $num = 0;
            for ($i = 0; $i < $len; $i++) {
                switch ($s[$i]) {
                    case 'M':
                        $num += 1000;
                        break;
                    case 'D':
                        $num += 500;
                        break;
                    case 'C':
                        $num += 100;
                        if($s[$i+1] == 'M'){
                            $num += 800;
                            $i++;
                        }elseif($s[$i+1] == 'D'){
                            $num += 300;
                            $i++;
                        }
                        break;
                    case 'L':
                        $num += 50;
                        break;
                    case 'X':
                        $num += 10;
                        if($s[$i+1] == 'C'){
                            $num += 80;
                            $i++;
                        }elseif($s[$i+1] == 'L'){
                            $num += 30;
                            $i++;
                        }
                        break;
                    case 'V':
                        $num += 5;
                        break;
                    case 'I':
                        $num += 1;
                        if($s[$i+1] == 'X'){
                            $num += 8;
                            $i++;
                        }elseif($s[$i+1] == 'V'){
                            $num += 3;
                            $i++;
                        }
                        break;
                        default:break;
                }
            }
            return $num;
        }

        /**
         * 14. 最长公共前缀
         * @param Array $strs
         * @return String
         */
        function longestCommonPrefix14($strs) {
            $count = count($strs);
            if($count < 1){
                return '';
            }
            $len = strlen($strs[0]);
            $matchMap =[];
            $keywords = '';
//            遍历第一个字符串作为字典
            for($i = 0; $i < $len; $i++) {
                if($i == 0){
                    $matchMap[$i] = $strs[0][$i];
                }else{
                    $pre = $i - 1;
                    $matchMap[$i] = $matchMap[$pre] . $strs[0][$i];
                }
//                当前匹配串为$matchMap[$i]
                foreach ($strs as $str) {
                    $pos = 1;
                    if(strpos($str, $matchMap[$i]) !== 0){
                        $pos = 0;
                        break;
                    }
                }
//                成功全部匹配
                if($pos){
                    $keywords = $matchMap[$i];
                }
            }
            return $keywords;
        }

        /**
         * 20. 有效的括号
         * @param String $s
         * @return Boolean
         */
        function isValid20($s) {
            $pos = true;
            $len = strlen($s);
//            空字符串直接匹配成功
            if($len == 0){
                return $pos;
            }
            $count = 0;
            $map = [];
            for($i = 0; $i < $len; $i++) {
                switch ($s[$i]) {
                    case ')':
                        if($map[$count-1] != '('){
                            $pos = false;
                        }
                        $count--;
                        break;
                    case ']':
                        if($map[$count-1] != '['){
                            $pos = false;
                        }
                        $count--;
                        break;
                    case '}':
                        if($map[$count-1] != '{'){
                            $pos = false;
                        }
                        $count--;
                        break;
                    default:
                        $map[$count] = $s[$i];
                        $count++;
                        break;
                }


            }
            var_dump($count);
            if($count != 0){
                $pos = false;
            }
            return $pos;
        }

        /**
         * 21. 合并两个有序链表
         * @param ListNode $list1
         * @param ListNode $list2
         * @return ListNode
         */
        function mergeTwoLists21($list1, $list2) {

        }

        /**
         * 26. 删除有序数组中的重复项
         * @param Integer[] $nums
         * @return Integer
         */
        function removeDuplicates26(&$nums) {
            $count = count($nums);
            for($i = 0; $i < $count; $i++) {
                if($nums[$i] == $nums[$i-1]){
                    unset($nums[$i-1]);
                }
            }
            $nums = array_values($nums);
            return count($nums);
        }

        /**
         * 27. 移除元素
         * @param Integer[] $nums
         * @param Integer $val
         * @return Integer
         */
        function removeElement27(&$nums, $val) {
            $count = count($nums);
            for($i = 0; $i < $count; $i++) {
                if($nums[$i] == $val){
                    unset($nums[$i]);
                }
            }
            return count($nums);
        }

        /**
         * 28. 找出字符串中第一个匹配项的下标
         * @param String $haystack
         * @param String $needle
         * @return Integer
         */
        function strStr28($haystack, $needle) {
            $pos = strpos($haystack, $needle);
            return $pos !== false? $pos : -1;
        }

        /**
         * 35. 搜索插入位置
         * @param Integer[] $nums
         * @param Integer $target
         * @return Integer
         */
        function searchInsert35($nums, $target) {
            $l = 0;
            $r = count($nums)-1;
            while($l <= $r){
                $mid = intval(($l+$r)/2);
                if($nums[$mid] == $target){
                    return $mid;
                }elseif ($target < $nums[$mid]) {
                    $r = $mid - 1;
                }else{
                    $l = $mid + 1;
                }
            }
            return $l;
        }

        /**
         * 58. 最后一个单词的长度
         * @param $s
         * @return int
         */
        function lengthOfLastWord58($s)
        {
            $len = strlen($s);
            for($i = $len-1,$count = 0;$i >= 0; $i--) {
                if($count == 0 && $s[$i] == ' '){
                    continue;
                }
                $count++;
                if($s[$i-1] == ' '){
                    break;
                }
            }
            return $count;
        }

        /**
         * 66. 加一
         * @param Integer[] $digits
         * @return Integer[]
         */
        function plusOne66($digits) {
            $count = count($digits);
            if($digits[$count - 1] != 9){
                $digits[$count - 1]++;
                return $digits;
            }
            for($i = $count - 1 ; $digits[$i] == 9 ; $i--) {
                $digits[$i] = 0;
                $count = $i;
            }
            if($digits[$count-1]){
                $digits[$count-1]++;
            }else{
                array_unshift($digits, 1);
            }
            return $digits;
        }



    }
    $solution = new Solution();
    $a = "10101";
    $b = "110000";
   var_dump($solution->addBinary67($a, $b));


?>

